package com.shuang.backtracking10;

import java.util.*;

public class FindSubsequences {
//    //方法一：Set集合去重法
//    //定义全局变量
//    List<List<Integer>> result = new ArrayList<>();
//    List<Integer> path = new ArrayList<>();
//
//    public List<List<Integer>> findSubsequences(int[] nums) {
//
//        //递归回溯处理
//        backTracking(nums, 0);
//
//        return result;
//    }
//
//    private void backTracking(int[] nums, int startIndex) {
//
//        //当存的序列集合大于等于2时存到结果集合中
//        if (path.size() >= 2) {
//            result.add(new ArrayList(path));
//            //不要return 符合条件的节点都要存到结果集
//        }
//
//        //终止条件可以不加 递归每次进去开始索引都会是i+1 循环肯定会结束
//        if (startIndex >= nums.length){
//            return;
//        }
//
//        //使用Set集合进行去重
//        HashSet<Integer> hs = new HashSet<>();
//
//        //for循环
//        for (int i = startIndex; i < nums.length; i++) {
//
//            //判断 如果不是递增序列（当前取值元素小于路径集合存的最后一个元素） 并且当前层重复取值了跳过本次循环
//            if (!path.isEmpty() && path.get(path.size() - 1) > nums[i] || hs.contains(nums[i])) {
//                continue;
//            }
//
//            //路径集合存值
//            path.add(nums[i]);
//            //去重集合hs存值
//            hs.add(nums[i]);
//            //递归
//            backTracking(nums, i + 1);
//            //回溯
//            path.remove(path.size() - 1);
//        }
//    }

//    class Solution {
//
//        //方法二：标记数组 去重法
//        private List<Integer> path = new ArrayList<>();
//        private List<List<Integer>> res = new ArrayList<>();
//
//        public List<List<Integer>> findSubsequences(int[] nums) {
//            backtracking(nums, 0);
//            return res;
//        }
//
//        private void backtracking(int[] nums, int start) {
//            if (path.size() > 1) {
//                res.add(new ArrayList<>(path));
//            }
//
//            int[] used = new int[201];
//            for (int i = start; i < nums.length; i++) {
//                if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||
//                        (used[nums[i] + 100] == 1))
//                    continue;
//                used[nums[i] + 100] = 1;
//                path.add(nums[i]);
//                backtracking(nums, i + 1);
//                path.remove(path.size() - 1);
//            }
//        }
//    }

    class Solution {

        //方法三：map集合去重法
        //结果集合
        List<List<Integer>> res = new ArrayList<>();
        //路径集合
        LinkedList<Integer> path = new LinkedList<>();

        public List<List<Integer>> findSubsequences(int[] nums) {
            getSubsequences(nums, 0);
            return res;
        }

        private void getSubsequences(int[] nums, int start) {
            if (path.size() > 1) {
                res.add(new ArrayList<>(path));
                // 注意这里不要加return，要取树上的节点
            }
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = start; i < nums.length; i++) {
                if (!path.isEmpty() && nums[i] < path.getLast()) {
                    continue;
                }
                // 使用过了当前数字
                if (map.getOrDefault(nums[i], 0) >= 1) {
                    continue;
                }
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
                path.add(nums[i]);
                getSubsequences(nums, i + 1);
                path.removeLast();
            }
        }
    }
}
